{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一.基本思路：局部距离替换高维空间距离\n",
    "\n",
    "上一节MDS中，我们构建原始高维空间的距离直接采用了欧氏距离，但这在流形结构数据中往往有问题，如下图所示，黑线长度便是欧氏距离，而采用红线来表示距离可能会更加合理\n",
    "![avatar](./source/19_isomap1.png)\n",
    "所以核心问题便是如何计算红色线距离，这可以转换为计算近邻图上两点之间的最短距离问题，操作如下：   \n",
    "\n",
    "（1）对样本中的每个点，保留与它最近的$k$个点（或者$\\varepsilon$领域半径内的点）的欧氏距离，而其他点的距离设置为无穷大；   \n",
    "\n",
    "（2）采用Dijkstra算法或者Floyd算法计算所有样本中任意两点间的最短距离，并更新原始距离矩阵$D$；  \n",
    "\n",
    "而后面的操作同MDS一样，所以这一节的主要操作便是对$D$再运用一次Dijkstra算法/Floyd算法，关于这俩算法这一节就介绍了，笔者可能会放在后续的《数据结构与算法》项目中再做介绍，哈哈哈~\n",
    "\n",
    "### 二.代码实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "from mpl_toolkits.mplot3d import Axes3D\n",
    "import numpy as np\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def floyd(dist_matrix):\n",
    "    vex_num=len(dist_matrix)  \n",
    "    for k in range(vex_num):\n",
    "        for i in range(vex_num):\n",
    "            for j in range(vex_num):\n",
    "                if dist_matrix[i][k]==np.inf or dist_matrix[k][j]==np.inf:\n",
    "                    temp=np.inf\n",
    "                else:\n",
    "                    temp=dist_matrix[i][k]+dist_matrix[k][j]\n",
    "                if dist_matrix[i][j]>temp:\n",
    "                    dist_matrix[i][j]=temp\n",
    "    return dist_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "造伪数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 200\n",
    "r = np.linspace(0,1,n)\n",
    "l = np.linspace(0,1,n)\n",
    "\n",
    "t = (3 * np.pi) / 2 * ( 1 + 2 * r )\n",
    "x =  t * np.cos(t)\n",
    "y = 10 * l\n",
    "z =t * np.sin(t)\n",
    "data=np.c_[x,y,z]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构建原始距离矩阵$D$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "m=data.shape[0]\n",
    "D=np.zeros(shape=(m,m))\n",
    "for i in range(0,m):\n",
    "    for j in range(i,m):\n",
    "        D[i,j]=np.sqrt(np.sum(np.power(data[i]-data[j],2)))\n",
    "        D[j,i]=D[i,j]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用floyd算法进行更新"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "epsilon=10#领域半径\n",
    "D=np.where(D<epsilon,D,np.inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "D=floyd(D)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用MDS算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "os.chdir('../')\n",
    "from ml_models.decomposition import MDS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAHr9JREFUeJzt3X+MHGd5B/Dvc+t1sjZtzlEOiBeMDQoOCS6+5hS1sopIimIgLbkkCg6qKv5AMkikEhSsXgoiBoFywiAjtZQSpAiQSn5ICReDES7BoaksUbB1hsQkVk2cEK+jxBRfIPHG2bt7+sfu2HN77zs7Mzvv/Px+JMt3u3u3s7u3z7z7fZ95R1QVRERUfiNZbwAREaWDBZ+IqCJY8ImIKoIFn4ioIljwiYgqggWfiKgiWPCJiCqCBZ+IqCJY8ImIKmJF1hvgd8kll+j69euz3gwiokI5dOjQ71R1bNDtclXw169fj4MHD2a9GUREhSIiz4S5HSMdIqKKYMEnIqoIFnwioopgwSciqggWfCKiishVlw5RFmZmW9i17yhOzrWxdrSBHVs3YnK8Gfp6oqJgwafCGKYw266bmW3h9gcfQ7uzAABozbVx+4OPAUDo66PeJ1FWWPApV1wUZgDW63btO3ruck+7s4Bd+45icrwZeH3Q7w26jjsEyork6Zy2ExMTygOvyi9sUQeARr2GO2/ahF37jqI11172u5qjDRyYuhZbpvdbrwdgve7kXBumd4AAOD59PTZM7bVev3a0Ees+D0xdG/hYB31yIOonIodUdWLQ7TjCp1QFjcSDRtMnDcUTwLnLB11vu85WtNf2inbQ9XHvEwh+rEDwpwPuDCgudumQEzOzLWyZ3o8NU3uxZXo/ZmZbAOIXda8A9/MXZtv1Qdft2LoRjXptyeWNeg07tm4EgMDr496n95hMTs61A58jb4fZ6n0y8XYG3vML2J97IhZ8SlxQUYpb1IcpzEHXTY43cedNm9AcbUDQjVy8WAVA4PVx79N7TLbHGndnAAQ/90SMdGgopnghqCgFRSQ7tm405tr+yMIWZQy6ftDPBkUituuHuc+gx2qbrwgTIw3aITAKqjZO2lJstonH/oLjEQC7t23mZGWPi8lr2ySz9ztszzsVGydtKVFRRvI1ESwYBhJrRxuhRupVKUBxPznYPhkA9knmmkhg+2mVdrRVxhE+DRR1JG+6nqPJ5Aw62CvpT12Uf2FH+Cz4NJCtx902km/6PgFwxJg+26exOMcM8HUsBkY6FIupWNgmChdUjSN5ryiwMGTD9tzboqBP3HfY+Hu8Dp+go4WpWNiWSefYWvouatSNt/daFG0tjZQfQe2lthbRoNwfYL9/ETHSoXNs0c2aVXW80llkxltSzP2Lj5EOBYoS3cyd6WD3ts3MckvK1hUUdDwA+/2LiSP8CrKN6C5YMYK5dmfZ7b0eb6qWoOMBPnHfYfb750jYET4z/Aqyjc5EELgcAFWLi9yfssVIp+QY3dAwbB0/tqUhbLn/ybk2D+7KgUQiHRG5G8DfAHhBVd/eu+xiAPcBWA/gaQAfUNXTQb+HkU6yGN2QS1H6/Tnx71bak7bfAvCvAL7ju2wKwE9UdVpEpnrf/1NC90ch2KKbC+sj1v55orCi9PurInBpB0pHIgVfVR8VkfV9F98A4F29r78N4KdgwXeqf8RlGmkBjG7IHVvHj+3gLkY96UqsS6dX8H/gi3TmVHXUd/1pVV0T9DsY6cRnim8EMHZSMLqhtPEYD7cK04cvItsBbAeAdevWZbw1xdE/Knr57Pyyj8yK5UWf0Q1lwTbJa4t6Pvf9Ixz1O+CyLfN5EbkUAHr/v2C6karepaoTqjoxNjbmcHPKw7QEgmkSFugWey59QFmztXi+aPm7PX2mw7N2OeByhL8HwIcATPf+f8jhfVWKaTLWhvEN5YVpktfW1dOPE7zJSKTgi8g96E7QXiIiJwDcgW6hv19EPgzgtwBuSeK+qiZKH30/xjeUd6aoxybs3z3ZJdWl80HLVX+dxO+vqv6JWP/qlaYIZ82qOlatXMHckwrD1NXz8tl549/32tEGO3qGlPmkLdlF7aO/42+v5B8/FU5/1GM7YPCay8e4Pv+QuJZOjgUtgcB16KmsbBO8jzx5iuv0DImrZeaIqdWSSyAQdW2Y2mtdoVOASkc8XC2zYEytli+/Oo/6iCy5HSdiqapsK3QCYPtmSCz4OWHK6zsLitdcuILRDRG6HT39y3f3Y8QTjJO2ORGU189+9rqUt4Yof/o7emzxTmuujS3T+9nJY8CCnyF/Zj8iggXDfErQx1iiqvF39NjW5xHg3OXs5FmKkU5G+jN7U7FnXk9kZ4p4TAsGMuY5jwU/I7blEWoizOuJQjC1b9piHh6l28VIJyO2P8BFVRyfvj7lrSEqpv6Dtmwxz+iqOnN9sOCnpr/H3rY8AjN7ovhMa/PUa4KXXpnH6TPd91uVc31GOilgjz1ROkwxz+qVK9BZXBr2VDXX55G2KQg62w8XOyNyK+gI3eZooxTvv8Kc8aoK2GNPlB3b+Z2r2L7JSMeRmdkWtkzvx4apvRgRMd6GeT2Re2zfPI8jfAf6l3dljz1Rdkxr7tvOslX29k1m+A7YMvuaCBZVC58XEhVd2d6jzPAzxB57onyznVrR+zRe1kyfBT8hXBeHqDj6Yx7Te7aMJ05nwU8AM3ui4vEfpbthaq/xNmXL9NmlkwCui0NUbLZP3yMi2DC1F1um95fixCoc4SeAmT1RsVUl02fBj4mZPfn/BkZX1aEKvNjuDPV10bpDyqIqmT7bMmPoz+xNGvUaY5ySMBX2uXbHePBOErzfu4Y7hcwU7YTpbMt0KCizL2IPL3WFKezeiouAm2Lv/73++/J/3Zpr4+P3HcY/P/grrFxR407AgaCDs/wnTAeKFfFwhB+Dbe8vADP7gvGKfGuu7WzEnhZv+5ss/kML8yke6D7XB6auTWmr7DjCTxgz+/KwFfkiF3vg/PbzE8Dwwp4wvWhtm85H+CLyNIA/AlgAMB+0F8rrCJ+ZffGVaSQ/jNFGHTvffyX/TiPK+1IMYUf4aRX8CVX93aDb5rXg5/3FJrM0ivygCdYoX7ucCDZtM6Of8PI+6GOkkyD22ReHq7jGVNhd7OiDWj3PdhZwprM49H30Rz879xzhqH+AsrRtpjHCPw7gNLp/Z99Q1btsty3aCD8vEzZVl+RIPq3CHpfLFlHGPeHlrXEjT5HOWlU9KSKvBfBjAP+gqo/6rt8OYDsArFu37qpnnnnG6fZEEVRImNnnQ9huiiBliDhmZlv43PePLGnfjKMMz0UabINAIJvnLjcFf8mdiewE8JKqftl0fZ5G+KZCwjdDfvh3xnGU9bXs/wQwTAwkAP7uL9bhC5Obkt3IEhg00Eh7QJiLgi8iqwGMqOofe1//GMDnVfVHptvnqeAzxsmnYUayZS3ygwwbeTHqMRs06EizVuSl4L8ZwPd6364A8F1V/aLt9nkq+HnL6KpsmIJV1SJvE3eHyefRLg+1IhddOqr6FIB3uLyPpHnFxVZUeHBVuvo/Oocp9ixOdt4a8FELv7+z5xP3HcbBZ37PqKfHtgyDopsU5OlvkEsr+OQtl6uyuBk9i3w0w8yFMOrpykPdyMUIv2hsi6IBLCRpitN5w51xPP6zPn1m5jH8x89+Gzoym2t3CrmAWNL8PfqmHWee+vN5xisf2wFWAuDA1LW5eMHKbma2hU/e/8tIxX60UWexT8AXJjdh97bNWLOqHvpnvGJWdZPjTRyYuhZiuT4va+5whO9jy+KY27sVdVKWGb07/ow/bNSTl2KWB3nP81nwMfgAK5583J2ok7Is8umIEvVwQHSe7VSJQD7W0K98wTcVHI4g0+HFN6alpvsxo8/OFyY3YeJNFxu7ejggWirveX7lM3zTRK1X7Jnbu+PtaMMU+5oIi33GJsebmP3sdfjqts1ojjYg6L5H+Losl+c8v/IjfNuTz1zSjahtgBzZ54s/6qFgeczzKz/Ct+WPzCWT543qBxV7b2TEESQV2Y6tG9Go14zXeXn+zGwr1W2q7AifE7XpCpvX10TwlQ+8g0WeCi+PeX4lR/j9I01vohbgqNKFsHl9o15jsadSyVueX8mCz4na9IQ9kIo7WiozW0Q8IpJqrFPJgs+J2nSEGdk36jV8ddtm7mip1Gx5/oJqqll+pTJ8roSZjrCdOGy3pKrw/sZN81hpZvmVGeEP6hDhRG0ywnbiMK+nqpkcb2LR8mk3rXShMgV/0EqYHGkOL2xez5E9VVXWbeCVKfhcCdMtduIQDWbK8gXANZePpXL/lSj4M7MtjIi5MYq5fTKCPkF5+EmKqm5yvImbr2ouadNUAA8caqUycVv6SdugkSdz+2TMzLYCM3suj0B03iNPnlrWOJLWxG3pR/i2kSdz5GR4O1QbPs9ES2XZFl76gm97EhdVWYSGNGiSlnk90XK2GHk0wpnG4ip9wc96VryswkzScmRPtNyOrRtRry2fU3zplXnnOX5pC/7MbAtbpvefWxzNj9n9cMK0XzZHGyz2RAaT402sXrl8+rSzqM7PD1zKSVuexcqdsMslcIdKZPdiu2O83HWOX8qCP2hxNIpvUPslJ2mJBrOdHMV1jl/KSIeLo7kRpv2Sk7REg2WV4zsv+CLyHhE5KiLHRGTK9f0BnKh1ge2XRMnJKsd3WvBFpAbgawDeC+AKAB8UkStc3ifQPUyZE7XJYfslUfKyyPFdj/CvBnBMVZ9S1VcB3AvgBpd3ODPbwgOHWkuOZBMAN1/Fky/HwfZLIjeySCJcF/wmgGd935/oXeaMbcL2kSdPubzb0ho0Scv2S6J4slhIzXXBN61YtmSoKCLbReSgiBw8dWr4oswJ2+SEmaRlTEYUTxYLqbku+CcAvNH3/RsAnPTfQFXvUtUJVZ0YGxt+z8YJ22RwkpbIvaCF1FxwXfB/AeAyEdkgIisB3Apgj8s7NH1M4kg0Gk7SEqUj7UTCacFX1XkAtwHYB+AJAPer6hFX9+edS7XdWUCtt/4912CPhpO0ROlJO5Fw3oevqj9U1beq6ltU9Yuu7qf/XKoLqudG9ixO4XGSlig9tglaVxO3pTnS1lSoXGZhZcVJWqL02LoHXXUVlqbgsztneDOzLWNbFcBJWiIXSpXhp4ndOcPbte/oso4BoNtby0laouSVLsNPC5dTGE5Qz70CLPZEDqRdt0pR8LmcwnAG9dw3+SmJKHFZ1K1SFHwupzCcoM4cfkoiciOLulWKgs8J2+EEdeZwopbIjSzqVikKPids4wvqzGHPPZE7ZVwtMxWcsI0vqDOHzx+RO2kfdAWUoOBzwnY47MwhykbaB10BJSj4nLCNb1CcQ0TuMMOPgRO28THOIcoOM/wYOGEbH+McouxkMfdY+ILP9e/jYZxDlJ2s5h4LX/C904R569/XRDhhGwLjHKLsZDX3WPiC7+0pvRN2LKg6PSdkWdjmOBjnELmX1dxj4Qs+18GP56JG3Xj5qOVyIkrGzGwLI2IOVF3PPRa+4LNLJx7L35v1ciIaXtApRNOYeyx8wWeXTjynz3SMl89ZLiei4dkWKkzrBEOFL/g7tm5EfWTpsLQ+Ipx4DBDUocMdJZE7tuRhUTWVubPCF3wAWFa9GEsEYocOUTZGV5nnyNIaaBW+4O/adxSdhaXlq7OgnLQNwA4dovTNzLbw0ivzyy6v19JLJApf8DlpGx07dIjSt2vfUXQWl3+2Xr1yRWoDrcIXfE7aRscOHaL02QahL7bTa5QofMHn0grR2Tpx2KFD5E4eBqeFL/hcWiE6W6Rju5yIhjMz28LLZ5fn92kPTgtf8Lm0QnSMdIjS4x1sNdcX3axZVU/9nNHOCr6I7BSRlogc7v17n4v74dIK0THSIUqP7WCrVSlO1npWOP79u1X1yy7vgF060V3UqC8bbXiXE1Gy8lSjCh/p5GEipGgY6RClI8uF0kxcF/zbRORXInK3iKwx3UBEtovIQRE5eOpU9LWgubRCdIx0iNzLeqE0k6EKvog8LCKPG/7dAODrAN4CYDOA5wB8xfQ7VPUuVZ1Q1YmxsbGYGzLge1rCNrJgpEOUnKwXSjMZquCr6rtV9e2Gfw+p6vOquqCqiwC+CeDqZDZ5KS6tEJ3pUxEAvPzqPLubiBKS9UJpJi67dC71fXsjgMdd3E+eJkSKYnK8iddcuHy+njtKouHNzLawZXq/cYFCINv5RZddOl8Skc3orsn1NICPuLiTtaMNtAzFnZO2wWx5PXeURPF5ub0pygGyXwXA2QhfVf9eVTep6p+p6vtV9TkX98OlFeLh0bZEybPl9gDQHG1klt17XPfhO+c9eTv3HDnXW35hvfDdps6xNZMoebZPyALgwNS16W6MQeELvufs/OK5r0+f6eD2Bx8DwPXdbWyRju3Uh0RkNzPbsp5YCMhPxFyKoTCXV4jO9gcoADt1iCLwcnvTXCKQr4i5FAWfnTrR7di60Xi4ggLcURJFkPfc3q8UBZ/LK0Q3Od60fvy0jVSIaLlBuX1eij1QkoJv6tQBgDM8kChQk7EOUWx57re3KUXBnxxv4s6bNi07J6s3ecviZcZYhyieIuX2fqUo+EC36K++YHnTESdv7YJiHc5/ENkVKbf3K01bJsDJ2zialiOVeQAWkV3e++1tSjPCBzh5GwcXUiOKrqi1plQFn8ssRMeF1IiiycsJyeMoVcE3Td5ymYXBbEfdtubaHOUT+eTphORxlLIampZZYOGyC/oYyueO6Lw8nZA8jtIVfC6zEJ3tOAaAzx2RX9EbQ0pX8Iv+gmTBi8JsGO0QdRV1stZTuoJf9BckK5PjTeuRtwCjHaIiT9Z6SlfwucxCfIx2iMyKPlnrKV3B5zIL8THaITIr+mStp3QFH+AyC8NgtEO0XFnmBktZ8IHyvEBZYLRDtFRZ5gZLW/DL8gJlYVC0w50mVYW3BHJrrr1sZdkiTdZ6SlvwTaNUAXDN5WPZbFDBBEU7IyKMdaj0+pdAVuBc0c/ziphBSlvwJ8ebuPmq5pK9sgJ44FCLxSokW7SzoMosn0rPNFGr6Bb7vJ3JKqzSFnwAeOTJU8vWe2cGHZ4X7dRk+WqafB6p7Mo4D1jqgl/GFyxtk+NNLKr5NCls06QyK+M8YKlOgNJvreXkHkV+wbJgex6BbpsmgEJ+vCXqNzPbwq59R3Fyro2LGnXUa4LOwvkBTxEnav2GGuGLyC0ickREFkVkou+620XkmIgcFZGtw21mPFwfPxls06Qq8E/SKtA9qla7R9MKijtR6ydq+bge6odF3gZgEcA3AHxKVQ/2Lr8CwD0ArgawFsDDAN6qquaTQPZMTEzowYMHY2+PSf8eW6S7/vva0QZ2bN1Y6BcvTTOzLXz8vsPW65t8PqngvPbLft4kbZ6JyCFVnRh0u6FG+Kr6hKqahnc3ALhXVc+q6nEAx9At/qmbHG/iwNS12L1tM87OL+L0mQ4U3fyZnSbhDToCl88nFV0V5vxcTdo2ATzr+/5E77LMcJ384QVFOwCfTyq2Mk7S9hs4aSsiDwN4veGqT6vqQ7YfM1xmzI5EZDuA7QCwbt26QZsTWxX23q55cc2ufUetk7he5w6jHSqCsk/S9htY8FX13TF+7wkAb/R9/wYAJy2//y4AdwHdDD/GfYXCjp1kTI43MTnetOadADt3qBi8SVrvk/9cu4P6iGDNqnpp5/lcRTp7ANwqIheIyAYAlwH4uaP7CoUdO8li5w4VnSnm7SwqVq1cgePT1xf2aNogw7Zl3igiJwD8JYC9IrIPAFT1CID7AfwawI8AfGxQh45r3lGjzdFGaVqsshRm7fwt0/s5iUu5VcWYd6i2zKS5aMskt4KiHaD7KYo7VsoLf2Y/IoIFQ/0rQhtmv1TaMonYuUNF0X9glanYlz3mLfXSCuRe2M6dDVN7SzkJRsVhO01hTQSLqpX4+2TBp6GF6dzxH+zm/QxRmmzZ/KIqjk9fn/LWZIORDiVmULwDdCOej993mBO65Jx3tqoNU3uxZXo/RlfVjberUms2R/iUGH+8c7KXk9pwtE8u9ffYt+baqI9I6Q+sGoQjfEqUt3bR8enrA9feATihS+7YeuxXr1xR6dZsjvDJmR1bNy4ZZZlwQpdcsOX1L7Y7OHzHdSlvTX6w4JMzYTp4AE7o0vD8/fVrRxsYXVXH6TOdZberUl5vwkiHnPIinq9u2xxqQpcRD0XV31/fmmvjpVfmUa8tXcOxanm9CQs+paJ/aQsbLslAUTGvD4+RDqXG69cHgpdkYLxDNv3RzY6tG5nXR8ARPmUizJIMn7z/l+d6qDniJ1N0c/uDj7G/PgIWfMqEP+KxWVDl6SjpHNtZ61TBpc9DYsGnzHgTuoP69QFO6FJwqyWXPg+HGT5lLky/PsCe/SoxZfVBZ63zzw+RHUf4lLn+Dp6a2Pt4GPGUny2rv+byMUY3Q+IJUCh3+tdBsanSsrZlZRrJ2w7Ua/qu99+er3v4E6Cw4FMu+QtBmL9QnlmreEw79ka9Zt3RC1CZZYyjYsGn0hh0GkXPaKOO1Res4OivIGyva61Epx5MS9iCz0lbyr2wk7pz7Q7m2t31U3jwVr5EOWBqQXXZSJ9ZfTI4wqdCCHPyaROO+rNni24urI8YFzhjVh8dIx0qrbCTuibM+t0xjeKDTn052qjj7Pzish0BX5/oGOlQafWfWWvtaANnXp03jhb7tTsL2LnnCEePCTOdYcqL1IIOmNq9bTNfixRxhE+lwFF/eqK2UgKwXsdJ2GQw0qHK6S9EYUf9ALN+E1NhBxC5lXL3ts3Gn+FONjks+FR5SYz6AZQ6crDl7lEnWge1Utruh5LBgk+E4Uf9tklFoFg7giij9Ttv2jTwtJQmplZKjuLTkUrBF5FbAOwE8DYAV6vqwd7l6wE8AcBb3vBnqvrRQb+PBZ9cG2bU74mzI0hjhJvUaL052gh9hLP/Z9hKmZ20Cv7bACwC+AaAT/UV/B+o6tuj/D4WfErDMKP+ILYdwc1XNfHAoVZiOwjXo3UBrCtTspUyn1KNdETkp2DBp4KKOgKOypZvx91BpDVat+1AgGLFWVWQhz78DSIyC+APAD6jqv9tupGIbAewHQDWrVvncHOIzEx9/UGj5qg7AttRwd4yEH7tzgLu+Z9nl/2M/wQwprM+2SIq7/FEGa37C7itsLPAF9PAEb6IPAzg9YarPq2qD/Vu81MsHeFfAOA1qvp/InIVgBkAV6rqH4LuiyN8ypso8UnUDpaovLMEcLRO/RIb4avqu6PeuaqeBXC29/UhEfkNgLcCYDWnQgk6k1LYHYEtoom6g/BOys3ROsXlJNIRkTEAv1fVBRF5M4DLADzl4r6IshBlRzA53sTEmy4eegcR9DM733+l9b4HbS9Vx1AFX0RuBPAvAMYA7BWRw6q6FcA7AXxeROYBLAD4qKr+fuitJco5W2FNYgfh/3mO1ikOHnhFRFRwYTN8nsSciKgiWPCJiCqCBZ+IqCJY8ImIKoIFn4ioInLVpSMipwA8M+SvuQTA7xLYnKzxceQLH0e+8HEs9SZVHRt0o1wV/CSIyMEw7Ul5x8eRL3wc+cLHEQ8jHSKiimDBJyKqiDIW/Luy3oCE8HHkCx9HvvBxxFC6DJ+IiMzKOMInIiKD0hR8EblFRI6IyKKITPguXy8ibRE53Pv371lu5yC2x9G77nYROSYiR0Vka1bbGJWI7BSRlu81eF/W2xSFiLyn95wfE5GprLcnLhF5WkQe670GhVmlUETuFpEXRORx32UXi8iPReR/e/+vyXIbw7A8jlTfG6Up+AAeB3ATgEcN1/1GVTf3/n005e2Kyvg4ROQKALcCuBLAewD8m4jU0t+82Hb7XoMfZr0xYfWe468BeC+AKwB8sPdaFNU1vdegSC2N30L3b95vCsBPVPUyAD/pfZ9338LyxwGk+N4oTcFX1SdU9WjW2zGsgMdxA4B7VfWsqh4HcAzA1eluXSVdDeCYqj6lqq8CuBfd14JSoqqPAug/n8YNAL7d+/rbACZT3agYLI8jVaUp+ANsEJFZEfkvEfmrrDcmpiaAZ33fn+hdVhS3iciveh9rc//x26foz7ufAvhPETkkItuz3pghvU5VnwOA3v+vzXh7hpHae6NQBV9EHhaRxw3/gkZczwFYp6rjAP4RwHdF5E/T2WKzmI9DDJflpsVqwGP6OoC3ANiM7uvxlUw3NppcP+8RbVHVP0c3nvqYiLwz6w2idN8bTs5p60pZTqge53GgO7J8o+/7NwA4mcwWDS/sYxKRbwL4gePNSVKun/coVPVk7/8XROR76MZVpjmvInheRC5V1edE5FIAL2S9QXGo6vPe12m8Nwo1wo9DRMa8yc2Cn1B9D4BbReQCEdmA7uP4ecbbFErvDem5Ed2J6aL4BYDLRGSDiKxEd+J8T8bbFJmIrBaRP/G+BnAdivU69NsD4EO9rz8E4KEMtyW2tN8bhRrhBynLCdVtj0NVj4jI/QB+DWAewMdUdSHLbY3gSyKyGd0o5GkAH8l2c8JT1XkRuQ3APgA1AHer6pGMNyuO1wH4nogA3ff9d1X1R9luUjgicg+AdwG4REROALgDwDSA+0XkwwB+C+CW7LYwHMvjeFea7w0eaUtEVBGlj3SIiKiLBZ+IqCJY8ImIKoIFn4ioIljwiYgqggWfiKgiWPCJiCqCBZ+IqCL+H4HrnbeX/BbnAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x233ff4f13c8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mds = MDS(n_components=2)\n",
    "new_data = mds.fit_transform(D=D)\n",
    "plt.scatter(new_data[:, 0], new_data[:, 1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码封装一下到`ml_models.decomposition.Isomap`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三.问题讨论\n",
    "显然，Isomap会受到最近邻$k$或者近邻半径$\\varepsilon$的影响，选择过大或者过小都有弊端：   \n",
    "\n",
    "（1）过小，可能会存在“断路”的情况，图中某些区域可能与其他区域不存在连接，直观来看就是距离矩阵通过floyd算法更新后还存在`np.inf`；  \n",
    "\n",
    "（2）过大，则会存在“短路”的情况，使得距离失真，比如本节最上图中的黑线距离会取代红线距离；\n",
    "\n",
    "在实际使用时通过后续任务的表现（分类/回归/...任务的具体表现）来选取"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
